import java.awt.Point;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Queue;
import java.util.Random;
import java.util.Set;
import java.util.concurrent.ConcurrentLinkedQueue;


public class MinesweeperPlayer2 {
	public static Collection<Point> solve(MinesweeperBoard board) {
		/**
		 * To store the suspected mines
		 */
		Set<Point> flags = new HashSet<Point>();
		/**
		 * Stores points I believe to be safe to reveal
		 */
		Queue<Point> knownSafePoints = new ConcurrentLinkedQueue<Point>();
		/**
		 * Stores points that have unrevealed neighbors
		 */
		Set<Point> pointsToExplore = new HashSet<Point>();
		/**
		 * so I can tell when I've examined all points but didn't find any
		 * changes to make
		 */
		
		//Point startPoint = new Point(0,2);
		Random random = new Random(System.currentTimeMillis());
		
		Point startPoint = new Point(random.nextInt(board.getWidth()),random.nextInt(board.getHeight()));

		pointsToExplore.add(startPoint);

		while (!gameWon(board, pointsToExplore, flags))
		{
			exploreFromPoint(startPoint, board, flags, knownSafePoints, pointsToExplore);
			if(!gameWon(board, pointsToExplore, flags)) {
				startPoint = guessPoint(board, pointsToExplore, knownSafePoints, flags);
				pointsToExplore.add(startPoint);
			}
		}
			return flags;
	} // end solve
	
	private static void exploreFromPoint(Point startPoint, MinesweeperBoard board,Set<Point> flags,Queue<Point> knownSafePoints,Set<Point> pointsToExplore)
	{
		Boolean setChanged = false;
		board.revealTile((int)startPoint.getY(), (int)startPoint.getX()); // will throw an exception if its a mine
		if( board.getTile((int)startPoint.getY(), (int)startPoint.getX()) == 0) {
			knownSafePoints.addAll(getNeighbors(startPoint, board));
			processKnownSafePoints(board, knownSafePoints, pointsToExplore);
		}
		else if( board.getTile((int)startPoint.getY(), (int)startPoint.getX()) > 0) {
			pointsToExplore.add(startPoint);
		}
		int iterationCount = 0;
		do {
			setChanged = false;
			iterationCount ++;
			Point[] points = pointsToExplore.toArray(new Point[pointsToExplore.size()]);
			for(int i = 0;i<points.length;i++)
			{
				if(setChanged == true){ 
					processLogic(points[i], board, knownSafePoints, pointsToExplore, flags);
				}
				else
					setChanged = processLogic(points[i], board, knownSafePoints, pointsToExplore, flags);
				if(!knownSafePoints.isEmpty()) {
					if (setChanged == true)
						processKnownSafePoints(board, knownSafePoints, pointsToExplore);
					else
						setChanged = processKnownSafePoints(board, knownSafePoints, pointsToExplore);
				}
			}	
		} while (setChanged == true);
		
	}
	
	private static boolean gameWon(MinesweeperBoard board, Set<Point> pointsToExplore, Set<Point> flags)
	{
		Queue<Point> frontier = new ConcurrentLinkedQueue<Point>();
		Iterator<Point> itr = pointsToExplore.iterator();
		while (itr.hasNext()) {
			Point p = itr.next();
			if(board.getTile((int)p.getY(), (int)p.getX()) == MinesweeperBoard.HIDDEN &&
					!(flags.contains(p)))
				frontier.add(p);
		}
		if(flags.containsAll(frontier) && flags.size()!= 0)
			return true;
		else
			return false;
	}
	
	private static boolean processKnownSafePoints(MinesweeperBoard board, Queue<Point> knownSafePoints, Set<Point> pointsToExplore) {
		boolean changed = false;
		while(!knownSafePoints.isEmpty()) {
			Point safePoint = knownSafePoints.poll();
			if(board.getTile((int)safePoint.getY(), (int)safePoint.getX()) == MinesweeperBoard.HIDDEN) {			
				board.revealTile((int)safePoint.getY(), (int)safePoint.getX());
				int value = board.getTile((int)safePoint.getY(), (int)safePoint.getX());
				if(value == 0){
					knownSafePoints.addAll(getNeighbors(safePoint,board));
					changed = true;
				}
				if(value > 0) {
					// add children to points to explore if they're hidden?
					pointsToExplore.addAll(getNeighbors(safePoint,board));
					changed = true;
				}
			}
		}
		return changed;
	}
	
	private static boolean processLogic(Point point, MinesweeperBoard board, Queue<Point> knownSafePoints, Set<Point> pointsToExplore,Set<Point> flags) {
		boolean changed = false;
		Queue<Point> unknownNeighbors = getNeighbors(point,board);
		int unknownCount = 0;
		int flagCount = 0;
		int value = board.getTile((int)point.getY(), (int)point.getX());
		Iterator<Point> itr = unknownNeighbors.iterator();
		while (itr.hasNext()) {
			Point neighbor = itr.next();
			if(flags.contains(neighbor)) {
				flagCount++;
				itr.remove();
			}
			else if (board.getTile((int)neighbor.getY(), (int)neighbor.getX())!= MinesweeperBoard.HIDDEN ) {
				itr.remove();
			}
		}// while
		unknownCount = unknownNeighbors.size(); 
		if(unknownCount == (value - flagCount )) {
			if(unknownNeighbors.size() > 0)
				changed = true;
			flags.addAll(unknownNeighbors);
		}
		else if (value == flagCount) {
			if(unknownNeighbors.size() > 0)
				changed = true;
			knownSafePoints.addAll(unknownNeighbors);
		}
		return changed;
	}
	
	private static Queue<Point> getNeighbors(Point point, MinesweeperBoard board)
	{
		Queue<Point> neighbors = new ConcurrentLinkedQueue<Point>();
		int[] neighborIndex = {-1,-1,-1,0,-1,1,0,1,1,1,1,0,1,-1,0,-1};
		for(int i = 0;i<neighborIndex.length;i+=2){
			int neighborX = (int)point.getX() + neighborIndex[i+1];
			int neighborY = (int)point.getY() + neighborIndex[i];
			if(neighborX >= 0 && neighborX < board.getWidth() && 
					neighborY >= 0 && neighborY < board.getHeight())
			neighbors.add(new Point(neighborX, neighborY));
		}
		return neighbors;
	}
	
	private static Point guessPoint(MinesweeperBoard board,Set<Point> pointsToExplore, Queue<Point> knownSafePoints, Set<Point> flags)
	{
		// from points to explore, make a collection of unrevealed tiles
		Point choice = null;
		double score = 1;
		
		Queue<Point> frontier = new ConcurrentLinkedQueue<Point>();
		Iterator<Point> itr = pointsToExplore.iterator();
		while (itr.hasNext()) {
			Point p = itr.next();
			if(board.getTile((int)p.getY(), (int)p.getX()) == MinesweeperBoard.HIDDEN &&
					!(flags.contains(p)))
				frontier.add(p);
		}
		Iterator<Point> n1Itr = frontier.iterator();
		while (n1Itr.hasNext()) {
			Point possibleChoice = n1Itr.next(); // point n1
			// neighbors (n2) of n1
			Queue<Point> n2List = getNeighbors(possibleChoice,board);
			// an array to hold 
			//Point[] n2PointsArray = new Point[n2List.size()];
			// holds the scores of the NON-HIDDEN children of the point I'm trying to rank
			// sum of these scores give a total score for possibleChoice
			double[] n2ScoresArray = new double[n2List.size()]; // need to find out how many non-hidden children
			Iterator<Point> n2Itr = n2List.iterator();
			int index = 0;
			while(n2Itr.hasNext()){
				Point p = n2Itr.next();
//				// only consider possibilities from among hidden tiles
				if(board.getTile((int)p.getY(), (int)p.getX()) != MinesweeperBoard.HIDDEN)
				{
					int value = board.getTile((int)p.getY(), (int)p.getX());
					int unkCount = 0;
					int flagCount = 0;
					Queue<Point> n3List = getNeighbors(p, board);
					Iterator<Point> n3Itr = n3List.iterator();
					while(n3Itr.hasNext()){
						Point n3 = n3Itr.next();
						if(board.getTile((int)n3.getY(), (int)n3.getX()) == MinesweeperBoard.HIDDEN)
							unkCount++;
						if(flags.contains(n3))
							flagCount++;
					}
					n2ScoresArray[index] = (double)(value-flagCount)/(double)(unkCount-flagCount);
					index++;
				}
			}
			// now sum the scores to get the totalScore for possibleChoice
			// then if that score is smaller than "score" replace "choice" and "score" with
			// possibleChoice and totalScore
			double totalScore = 0;
			int validCount = 0;
			for(int i=0;i<n2ScoresArray.length;i++)
			{
				totalScore += n2ScoresArray[i];
				if(n2ScoresArray[i] > 0)
					validCount ++;
			}
			totalScore = totalScore / validCount;
			if (totalScore < score) {
				score = totalScore;
				choice = possibleChoice;
			}		
		}
		// if there is only 1 revealed tile on the board, choice is null
		// will have to randomly choose one of that tiles 8 neighbors
		//System.out.println(pointsToExplore);
		if(choice == null)
		{
			// need an iterator to get at the point
			Iterator<Point> onlyPoint = pointsToExplore.iterator();
			Point basePoint = onlyPoint.next();
			Queue<Point> neighbors = getNeighbors(basePoint,board);
			// remove any non-hidden neighbors
			Iterator<Point> neighborItr = neighbors.iterator();
			while (neighborItr.hasNext()) {
				Point p = neighborItr.next();
				if(board.getTile((int)p.getY(),(int)p.getX()) != MinesweeperBoard.HIDDEN) {
					neighborItr.remove();
				}
			}
		
			Point[] pointArray = neighbors.toArray(new Point[neighbors.size()]);
			choice = basePoint;
			while(board.getTile((int)choice.getY(), (int)choice.getX()) != MinesweeperBoard.HIDDEN){
				Random random = new Random(System.currentTimeMillis());
				int randomNumber = random.nextInt(neighbors.size()-1);
				choice = (Point)pointArray[randomNumber];
			}
		}
		return choice;
	}
} // end class	

